#ifndef _SEARCH_TREE_H_
#define _SEARCH_TREE_H_

template <class T>
class CSearchTree
{
private:
	static const int SYMBOL_COUNT = 40;
	static const int MAX_KEY_LEN = 64;
	static const int STACK_DEPTH = 64;
	typedef struct _treeNode
	{
		T data;
		bool hasData;
		_treeNode *next[SYMBOL_COUNT];
		_treeNode *parent;
		char parentSym;
	}TTreeNode;

	TTreeNode* m_root;

	TTreeNode* m_searchItem;
	int m_stack[STACK_DEPTH];
	int m_stackPos;

public:
	CSearchTree()
	{
		m_root = CreateNode(NULL, 0);
	}

	~CSearchTree()
	{
		DeleteNode(m_root);
	}

	bool Add(char* key, T data)
	{
		TTreeNode* node = FindNode(key, true);

		if (!node)
			return false;

		node->data = data;
		node->hasData = true;

		return true;
	}

	bool Find(char* key, T& data)
	{
		TTreeNode* node = FindNode(key, false);

		if (node)
		{
			if (node->hasData)
			{
				data = node->data;
				return true;
			}
		}

		return false;
	}

	bool FindFirst(char *key, char* name)
	{
		for (int i=0; i<STACK_DEPTH; i++)
		{
			m_stack[i] = -1;
		}

		m_stackPos = 0;

		m_searchItem = FindNode(key, false);

		name[0] = 0;

		if (!m_searchItem)
			return false;

		if (m_searchItem->hasData)
		{
			GetName(m_searchItem, name);
			return true;
		}

		return FindNext(name);
	}

	bool FindNext(char* name)
	{
		name[0] = 0;

		if (!m_searchItem)
			return false;

		while (1)
		{
			m_stack[m_stackPos]++;

			int found = -1;

			while ((m_stack[m_stackPos] < SYMBOL_COUNT)&&(found<0))
			{
				if (m_searchItem->next[m_stack[m_stackPos]])
				{
					found = m_stack[m_stackPos];
				}
				else
				{
					m_stack[m_stackPos]++;
				}
			}

			if (found>=0)
			{
				m_stackPos++;
				m_stack[m_stackPos] = -1;
				m_searchItem = m_searchItem->next[found];

				if (m_searchItem->hasData)
				{
					GetName(m_searchItem, name);
					return true;
				}
			}
			else
			{
				if (m_stackPos == 0)
				{
					m_searchItem = NULL;
					return false;
				}
				else
				{
					m_stackPos--;
					m_searchItem = m_searchItem->parent;
				}
			}
		}

		return false;
	}

private:
	int GetSymbolPos(char c)
	{
		if ((c>='a')&&(c<='z'))
			return (c-'a');

		if ((c>='A')&&(c<='Z'))
			return (c-'A');

		if ((c>='0')&&(c<='9'))
			return (c-'0'+26);

		if (c=='_')
			return 36;

		if (c=='+')
			return 37;

		if (c=='-')
			return 38;

		return 39;
	}

	char GetSymbolChar(int pos)
	{
		char *s = "abcdefghijklmnopqrstuvwxyz0123456789_+-?";

		return s[pos];
	}


	TTreeNode* CreateNode(TTreeNode* parent, char sym)
	{
		TTreeNode* node = new TTreeNode;

		node->hasData = false;

		for (int i=0; i<SYMBOL_COUNT; i++)
		{
			node->next[i] = NULL;
		}

		node->parent = parent;
		node->parentSym = sym;
		return node;
	}

	TTreeNode* FindNode(char* key, bool create)
	{
		if (!key[0])
			return 0;

		int p = 0;
		TTreeNode *node = m_root;

		while (key[p])
		{
			int s = GetSymbolPos(key[p]);
			if ((node->next[s] == NULL) && create)
			{
				node->next[s] = CreateNode(node, s);
			}

			if (node->next[s])
			{
				node = node->next[s];
				p++;
			}
			else
			{
				return NULL;
			}
		}

		return node;
	}

	void DeleteNode(TTreeNode* node)
	{
		for (int i=0; i<SYMBOL_COUNT; i++)
		{
			if (node->next[i])
			{
				DeleteNode(node->next[i]);
				node->next[i] = NULL;
			}
		}

		delete node;
	}

	void GetName(TTreeNode* node, char* name)
	{
		int tmp_name[MAX_KEY_LEN];
		int tmp_pos = 0;

		while (node->parent)
		{
			tmp_name[tmp_pos++] = GetSymbolChar(node->parentSym);
			node = node->parent;
		}

		int pos = 0;
		while (tmp_pos)
		{
			name[pos++] = tmp_name[--tmp_pos];
		}

		name[pos] = 0;
	}
};

#endif //_SEARCH_TREE_H_
